package graph.unweighted.dfs.path;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: SingleSourcePath.java 
 * @Package graph.dfs 
 * @Description: 应用DFS解决单源路径问题
 *                  去掉visited[]数组，复用pres[]数组
 *                  pres[v]为-1表示没有被遍历过，如果记录了上一个节点的编号，同时也就表示遍历过了
 * @author CandyWall   
 * @date 2021年1月15日 上午11:37:25 
 * @version V1.0
 */
public class CandySingleSourcePath_v2 {
    private CandyGraph graph;        // 图
    private int s;
    private int[] pres;    // 记录深度优先遍历过程中某一个顶点的前一个顶点，同时记录顶点有没有被遍历过
    
    /**
     * 
     * @param graph ：图
     * @param s     ：图中一个顶点，作为单源路径的源
     */
    public CandySingleSourcePath_v2(CandyGraph graph, int s) {
        this.graph = graph;
        graph.validateVertex(s);
        this.s = s;
        pres = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            pres[i] = -1;
        }
        dfs(s, s);
    }
    
    /**
     * 深度优先遍历
     */
    private void dfs(int v, int pre) {
        pres[v] = pre;
        for(int w : graph.adjacentVertexes(v)) {
            if(pres[w] == -1) {
                dfs(w, v);  // 顶点w是从v这个顶点来的
            }
        }
    }
    
    /**
     * 判断顶点s到顶点t是否可达
     * @return
     */
    public boolean isConnectedTo(int t) {
        graph.validateVertex(t);
        return pres[t] != -1;
    }
    
    /**
     * 获取顶点s到顶点t的单源路径
     * @return
     */
    /*public ArrayList<Integer> getSingleSourcePath(int t) {
        if(!isConnectedTo(t)) {
            return null;
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        path.add(s);
        getSingleSourcePath(t, path);
        return path;
    }
    
    private void getSingleSourcePath(int v, ArrayList<Integer> list) {
        if(pres[v] == v) {
            return;
        }
        getSingleSourcePath(pres[v], list);
        list.add(v);        
    }*/
    
    /**
     * 获取顶点s到顶点t的单源路径
     * @return
     */
    public ArrayList<Integer> getSingleSourcePath(int t) {
        if(!isConnectedTo(t)) {
            return null;
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        int cur = t;
        while(cur != s) {
            path.add(cur);
            cur = pres[cur];
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }
    
    public int[] getPres() {
        return pres;
    }

    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        int s = 0;
        CandySingleSourcePath_v2 ssp = new CandySingleSourcePath_v2(graph, s);
        System.out.println("从顶点 " + s + " 出发的深度优先遍历的得出的单源路径为：" + Arrays.toString(ssp.getPres()));
        int t1 = 6;
        System.out.println("从顶点 " + s + " 到顶点 " + t1 + " 的路径为：" + (ssp.getSingleSourcePath(t1) == null ? "不可达" : ssp.getSingleSourcePath(t1)));
        int t2 = 5;
        System.out.println("从顶点 " + s + " 到顶点 " + t2 + " 的路径为：" + (ssp.getSingleSourcePath(t2) == null ? "不可达" : ssp.getSingleSourcePath(t2)));
    }
}
